(1) Field of the Invention
The present invention relates to a curved surface image processing apparatus for rendering a three-dimensional (3D) object using graphic information described by a non uniform rational B-spline (NURBS) function in the field of 3D computer graphics, and a method thereof.
(2) Description of the Background Art
With recent significant improvement in computer performance in the field of image processing, CAGD (Computer Aided Geometric Design) systems and geometric modeling systems have increasingly developed so as to handle free-form surfaces for representing complicated shapes. Among a number of representation methods for creating free-form surfaces, NURBS curves and NURBS surfaces have an advantage in their ability of representing smooth surfaces using fewer control points. In addition to the control points, use of NURBS curves and NURBS surfaces make it possible to change shapes locally because of a lot of parameters such as weights and knots as well as control points for controlling the shapes, and to represent conic sections such as circular arcs, straight lines and parabolas in an integrated manner. Because of such excellent representation ability, techniques for rendering image models created using NURBS data have been demanded.
Four conventional rendering techniques (A˜D) using NURBS data and their problems will be described below in this order.
First, as the technique A, the background art of the general processing of generating curved surface images using NURBS data will be explained.
FIG. 3A and FIG. 3B are diagrams showing examples of a NURBS curve and a NURBS surface. In FIG. 3A, a NURBS curve 31 is a parametric curve represented by a parameter u, and the shape thereof is controlled by a plurality of control points 32, weights on respective control points and a collection of knots (knot vector) that indicate how much influence respective control points have on a parametric curve with a variation in the parameter u. The control points 32 are not always located on the NURBS curve 31.
In FIG. 3B, a NURBS surface 33 is a parametric surface represented by parameters u and v, and the shape thereof is controlled by a plurality of control points 34, weights thereon and a collection of knots (knot vector), as in the case of the NURBS curve 31.
Generally, a NURBS surface S(u, v) is expressed by Equation 1.
                              S          ⁡                      (                          u              ,              v                        )                          =                                            ∑                              i                =                0                                            m                -                1                                      ⁢                                                  ⁢                                          ∑                                  j                  =                  0                                                  n                  -                  1                                            ⁢                                                                    B                                          i                      ,                      m                                                        ⁡                                      (                    u                    )                                                  ⁢                                                      B                                          j                      ,                      n                                                        ⁡                                      (                    v                    )                                                  ⁢                                  w                  ij                                ⁢                                  Q                  ij                                                                                        ∑                              i                =                0                                            m                -                1                                      ⁢                                                  ⁢                                          ∑                                  j                  =                  0                                                  n                  -                  1                                            ⁢                                                                    B                                          i                      ,                      m                                                        ⁡                                      (                    u                    )                                                  ⁢                                                      B                                          j                      ,                      n                                                        ⁡                                      (                    v                    )                                                  ⁢                                  w                  ij                                                                                        (        1        )            
In Equation 1, w is a weight and Q is a control point. Also, a function B here is referred to as a B-spline basis function, and expressed by Equation 2 and Equation 3 using de Boor-Cox recurrence formula.
                                          B                          i              ,              1                                ⁡                      (            t            )                          =                  {                                                    1                                                              (                                                            t                      i                                        ≦                    t                    <                                          t                                              i                        +                        1                                                                              )                                                                                    0                                                              (                                                            t                      <                                              t                        i                                                              ,                                          t                      ≧                                              t                                                  i                          +                          1                                                                                                      )                                                                                        (        2        )                                                      B                          i              ,              k                                ⁡                      (            t            )                          =                                                            t                -                                  t                  i                                                                              t                                      i                    +                    k                    -                    1                                                  -                                  t                  i                                                      ⁢                                          B                                  i                  ,                                      k                    -                    1                                                              ⁡                              (                t                )                                              +                                                                      t                                      i                    +                    k                                                  -                t                                                              t                                      i                    +                    k                                                  -                                  t                                      i                    +                    1                                                                        ⁢                                          B                                                      i                    +                    1                                    ,                                      k                    -                    1                                                              ⁡                              (                t                )                                                                        (        3        )            
In Equation 2 and Equation 3, k is a degree, t is a parameter, and ti is a knot.
The existing image processing of NURBS data has a problem that these equations require an extremely large amount of computation and thus causes a limited amount of NURBS data that can be represented by an image processing system that requires real time processing. In addition, a circuit for integrating such a system into hardware increases in size, which is an obstacle to miniaturization.
In order to reduce an amount of computation, a conventional curved surface image processing apparatus that performs the following processing on a cubic (degree=3) NURBS surface at a preprocessing stage (See Background Art 1, Japanese Laid-Open Patent Application No. 2001-218977, pp. 7–23, for example).
In this background art, the recurrence formulas of Equation 2 and Equation 3 are expanded into ordinary cubic equations without being calculated recursively, and by substituting knot vectors in these equations, coefficient matrices (4×4) for obtaining B-spline basis functions are computed. These coefficient matrices are calculated for all the control points that define a NURBS surface. On the other hand, in real-time processing, each point on a NURBS surface is computed using control points and a coefficient matrix with variation in parameters u and v.
In order to enhance the computation processing speed, the curved surface image processing apparatus according to this background art introduces a differential matrix obtained by multiplying a coefficient matrix by a matrix of Δu and Δv which are differentials of respective parameters u and v. It computes each point on a NURBS surface recursively using control points, a differential matrix and a knot vector with variation in parameters u and v.
Next, as the technique B, the background art for performing polygon division of a NURBS surface will be explained.
First, the common definition of a parametric surface such as a Bezier surface and a B-spline surface will be described. There are several types of free-form surfaces such as a Bezier surface and a B-spline surface, but a NURBS surface is widely used as a more popular representation style of free-form surfaces. In 3D space, a parametric surface is defined as a continuous sequence of points (x, y, z) on the surface using two parameters u and v.
More specifically, one 3D coordinate (x, y, z) is obtained for a pair of parameters u and v. In order to describe the relationship between them mathematically, control points having weights and basis functions are used. A control point is a 3D coordinate necessary for determining the location and the outline of the shape of a parametric surface, and the weight thereof is a parameter indicating how much influence the control point gives on the surface, or, more plain and simple, how much the surface is pulled by the control point. The 3D coordinate and the weight of the control point are described by a two-dimensional (2D) array having discrete indices i and j corresponding to the respective directions of the parameters u and v. The basis function is a function for corresponding the control points and the detailed shape of the parametric surface.
Here, a coordinate <P>=(px, py, pz) of a point on a curved surface for a pair of parameters u and v is expressed by the following equations, where the 3D coordinate of the control point is <Q[i][j]>=(qx[i][j], qy[i][j], qz[i][j]), the weight of the control point is qw[i][j], the basis function in the u direction is B[n][i](u), and the basis function in the v direction is B[m][i](v). Note that the mark < > indicates a vector.<P>=(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j]*<Q[i][j]>)/(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j])
Namely,px=(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j]*qx[i][j])/(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j])py=(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j]*qy[i][j])/(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j])pz=(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j]*qz[i][j])/(ΣΣB[n][i](u)*B[m][j](v)*qw[i][j])
Here, I=0, 1, 2, . . . , (I−1), j=0, 1, 2, . . . , (J−1), and the mark Σ indicates the sum of i and j in the above ranges. I is the number of control points in the u direction and J is the number of control points in the v direction. And n and m are degrees of the basis functions in the u direction and the v direction.
Considering a NURBS surface as a parametric surface, a basis function is defined by a knot vector as well as parameters and a degree (or an order).
This knot vector is a sequence of parameter values in ascending order of the values at certain intervals that characterizes the shape of a curved surface. Different basis functions can be defined using degrees and knot vectors different from each other in the directions of the parameters u and v. The basis functions B[n][i](u) and B[m][j](v) of a NURBS surface are expressed by the following Cox-de Boor's recurrence formula using the knot vector in the u direction (u[0], u[1], . . . , u[I+n+1]) and the knot vector in the v direction (v[0], v[1], . . . , v[J+m+1]).
As for the u direction,
                    B        ⁡                  [          n          ]                    ⁡              [        i        ]              ⁢          (      u      )        =                    [                              (                          u              -                              u                ⁡                                  [                  i                  ]                                                      )                    /                      (                                          u                ⁡                                  [                                      i                    +                    n                                    ]                                            -                              u                ⁡                                  [                  i                  ]                                                      )                          ]            *                        B          ⁡                      [                          n              -              1                        ]                          ⁡                  [          i          ]                    ⁢              (        u        )              +                                   [                                    (                                                u                  ⁡                                      [                                          i                      +                      n                      +                      1                                        ]                                                  -                u                            )                        /                          (                                                u                  ⁡                                      [                                          i                      +                      n                      +                      1                                        ]                                                  -                                  u                  ⁡                                      [                                          i                      +                      1                                        ]                                                              )                                ]                *                              B            ⁡                          [                              n                -                1                            ]                                ⁡                      [                          i              +              1                        ]                          ⁢                  (          u          )                    
In the above equation, the degree n is not 0. Since the above equation is a recurrence formula, the basis function of n=3 is obtained based on the basis function of n=2. Repeat of this calculation requires the basis function of n=0, but it is assumed here that the basis function B[0][i](u) of n=0 has the value 1 only when u is in the range of (u[i], u[i+1]), while it has the value 0 in other cases. Values of elements of a knot vector are same as values of indices or monotonously increase as the indices increase, and a coefficient expressed by a fraction in the above recurrence formula is defined to be 0 when a denominator is 0. The above recurrence formula may be represented using an order instead of a degree. An order is a value of a degree plus 1. As for the v direction, the following basis function is defined in the same manner.
                    B        ⁡                  [          m          ]                    ⁡              [        j        ]              ⁢          (      v      )        =                    [                              (                          v              -                              v                ⁡                                  [                  j                  ]                                                      )                    /                      (                                          v                ⁡                                  [                                      j                    +                    m                                    ]                                            -                              v                ⁡                                  [                  j                  ]                                                      )                          ]            *                        B          ⁡                      [                          m              -              1                        ]                          ⁡                  [          j          ]                    ⁢              (        v        )              +                                   [                                    (                                                v                  ⁡                                      [                                          j                      +                      m                      +                      1                                        ]                                                  -                v                            )                        /                          (                                                v                  ⁡                                      [                                          j                      +                      m                      +                      1                                        ]                                                  -                                  v                  ⁡                                      [                                          j                      +                      1                                        ]                                                              )                                ]                *                              B            ⁡                          [                              m                -                1                            ]                                ⁡                      [                          j              +              1                        ]                          ⁢                  (          v          )                    
When a NURBS surface is divided into polygons, a 3D coordinate <P>=(px, py, pz) needs to be obtained by substituting parameters necessary for the above recurrence formula.
For the sake of simplicity, a NURBS curve, not a NURBS surface, will be explained first. In FIG. 19, a NURBS curve 1901 is defined by a degree n=3, a plurality of control points (Q[0], Q[1], Q[2] and Q[3]), and a knot vector having 8 elements (u[0], u[1], . . . , u[7]). A parameter for drawing this NURBS curve 1901 is only u, and the 2D coordinate <P>=(px, py) is expressed as follows.<P>=(ΣB[n][i](u)*qw[i]*<Q[i]>)/(ΣB[n][i](u)*qw[i])px=(ΣB[n][i](u)*qw[i]*qx[i])/(ΣB[n][i](u)*qw[i])py=(ΣB[n][i](u)*qw[i]*qy[i])/(ΣB[n][i](u)*qw[i])
A NURBS curve is defined in 2D space which is easy to understand visually in FIG. 19 and the above equations, but it may be a NURBS curve in 3D space by adding the definition of a Z coordinate pz. The relationship between the number of elements of a knot vector, a degree and the number of control points can be obtained by the number of elements of the knot vector (I+n+1) where the degree is n and the number of control points is I. In a case of FIG. 19, the number of elements of the knot vector is 4+3+1=8. Also, in FIG. 19, the effective range of the knot vector for drawing the NURBS curve 1901 is a range of (u[3], u[4]). As mentioned above, at least 4 control points are necessary for drawing a NURBS curve of a degree n=3. Addition of one control point at a fixed degree n=3 means addition of one element of a knot vector, and thus the effective range of the knot vector for drawing the NURBS curve expands to a range of (u[3], u[5]). FIG. 20 shows a NURBS curve obtained by adding one control point. As shown in FIG. 19 and FIG. 20, a NURBS curve does not generally pass on control points. However, as mentioned later, a NURBS curve has control points as edge points if elements of a knot vector represent a rational Bezier curve.
Next, suppose that the NURBS curve as shown in FIG. 19 is approximated to two line segments. For that purpose, three points put on both ends and the midpoint of the NURBS curve are connected by straight lines. Position coordinates of the points on the NURBS curve can be obtained by substituting u[3] and u[4] and the midpoint between them (u[3]+u[4])/2, for example, as values of a parameter u, into the above equations because the effective range of the knot vector is (u[3], u[4]). In order to divide a NURBS curve 2001 as shown in FIG. 20 into two line segments, a value of a parameter u can be u[3], u[4] or u[5], for example, because the effective range of the knot vector is (u[3], u[5]). The number of control points and the number of divided line segments of the NURBS curve are not limited to this example, but can be set freely.
On the basis of the above description, suppose that a NURBS surface in 3D space is divided into plane polygons. FIG. 22 shows the simplest NURBS surface 2201. In FIG. 22, the degrees in both directions of u and v are n=m=3, and the number of control points in both directions u and v are I=J=4, namely, 4×4=16. Knot vectors in the directions of u and v are respectively (u[0], u1, . . . , u[7]) and (v[0], v[1], . . . , v[7]), and the numbers of elements of the knot vectors in the directions of u and v are both (I+n+1)=(J+m+1)=8. The effective ranges of knot vectors for drawing the NURBS surface 2201 are ranges of (u[3], u[4]) and (v[3], v[4]). Therefore, 9 points on the surface can be obtained using u[3] and u[4] and the midpoint between them (u[3]+u[4])/2 as values of u and v[3] and v[4] and the midpoint between them (v[3]+v[4])/2 as values of v. It is possible to divide the surface into 4 rectangle polygons using these nine points thereon. It may be divided into 8 triangle polygons, of course. The number of control points on a NURBS surface and the number of divided polygons are not limited to this example, but may be set freely (See Background Art 2, Japanese Laid-Open Patent Application No. 03-201073, for example).
Next, as the technique C, the background art in which a parametric surface such as a Bezier surface is subdivided into minute polygons to be handled will be explained.
As a method for displaying a 3D object including a parametric surface on a 2D image display apparatus, a method for approximating the object to a collection of minute plane polygons for rendering is generally used at present.
An object, that is a 3D image, represented smoothly in a form of a parametric surface such as a NURBS surface and a Bezier surface has a smaller amount of data than an object represented by a collection of polygons such as triangles, and thus has an affinity for transmission via a network which has recently developed rapidly.
As a common method for dividing a parametric surface into polygons, a method of generating plane polygons by directly obtaining points on the parametric surface with a discrete variation in a parameter value at regular intervals and combining a plurality of pairs of these points adjacent to each other is used. This processing is generally called “tessellation”.
FIG. 30 shows an example of a cubic (the order=4) rational Bezier surface that is a typical parametric surface. A cubic (the order=4) rational Bezier surface is expressed by Equation 4.
                                                                                                                                    B                      ⁡                                              (                                                  u                          ,                          v                                                )                                                              =                                                                                            UMQM                          T                                                ⁢                        V                                            =                                              U                        ⁢                                                                                                  ⁢                                                  M                          ⁡                                                      [                                                                                                                                                                Q                                    00                                                                                                                                                                        Q                                    01                                                                                                                                                                        Q                                    02                                                                                                                                                                        Q                                    03                                                                                                                                                                                                                                    Q                                    10                                                                                                                                                                        Q                                    11                                                                                                                                                                        Q                                    12                                                                                                                                                                        Q                                    13                                                                                                                                                                                                                                    Q                                    20                                                                                                                                                                        Q                                    21                                                                                                                                                                        Q                                    22                                                                                                                                                                        Q                                    23                                                                                                                                                                                                                                    Q                                    30                                                                                                                                                                        Q                                    31                                                                                                                                                                        Q                                    32                                                                                                                                                                        Q                                    33                                                                                                                                                        ]                                                                          ⁢                                                  M                          T                                                ⁢                        V                                                                              ⁢                                                                                                                                                                                  M                    =                                          [                                                                                                                                  -                              1                                                                                                            3                                                                                                              -                              3                                                                                                            1                                                                                                                                3                                                                                                              -                              6                                                                                                            3                                                                                0                                                                                                                                                              -                              3                                                                                                            3                                                                                0                                                                                0                                                                                                                                1                                                                                0                                                                                0                                                                                0                                                                                              ]                                                        ,                                      U                    =                                          [                                                                        u                          3                                                ⁢                                                  u                          2                                                ⁢                        u                        ⁢                                                                                                  ⁢                        1                                            ]                                                        ,                                      V                    =                                                                  [                                                                              v                            3                                                    ⁢                                                      v                            2                                                    ⁢                          v                          ⁢                                                                                                          ⁢                          1                                                ]                                            T                                                                                                    }                ⁢                                                      (        4        )            
A parametric surface is represented using two parameters u and v, where 0<=u<=1 and 0<=v<=1. Qij (i=0, . . . , 3, j=0, . . . , 3) is control points defining the shape of a Bezier surface, and there exist 4×4=16 points in a case of a cubic (the order=4) surface. Among the control points, Q00, Q30, Q03 and Q33 are located on the surface but other points are not located on the surface. Each control point includes a W element corresponding to weight in addition to X, Y and Z elements. Therefore, an arbitrary point P on a curved surface is represented by P(X(u, v)/W(u, v), Y(u, v)/W(u, v), Z(u, v)/W(u, v)). Also, it is known that a Bezier surface has convex hull property and thus the surface is completely contained by a polyhedron that is formed by the control points.
An object is represented by a collection of the above-mentioned parametric surfaces. Such parametric surfaces that form an object are hereinafter referred to as patches for explanation. If an object is represented by approximation of each patch using a lot of small polygons, the object can be rendered with high definition. However, the calculation load increases as the number of polygons to be processed increases. Therefore, a method for rendering an object with high definition while restraining an amount of polygon generation needs to be established.
For that purpose, a background art suggests a method for calculating smoothness of each divided patch every time a surface patch is divided into a left surface patch and a right surface patch, and dividing the patch again if the smoothness is a permissible value or more, and then repeating the division of the patch until the smoothness thereof becomes less than the permissible value (See Background Art 3, Japanese Laid-Open Patent Application No. 11-007544, pp. 11–14, for example).
There is another method of generating an edge by connecting edge points of control points, calculating a vector from the midpoint of the edge to the midpoint on a curved surface that represents the surface of a polygon, as a deviation vector of a chord, and thus determining resolution depending on the length of the vector on a screen obtained by perspective transformation of the deviation vector of the chord (See Background Art 4, Japanese Laid-Open Patent Application No. 2001-52194, p. 5, for example).
Next, as the technique D, the background art for calculating a normal of each control point that defines a subdivided surface patch will be explained.
A Bezier surface obtained as a result of parameter transformation of a NURBS surface by knot insertion forms a Bezier surface of the degree bi-n if (n+1)×(n+1) control points are given. But it is just referred to as a Bezier surface of the degree n here. In the field of 3D computer graphics, a cubic Bezier surface is heavily used because of its easy controllability (See Background Art 10, “Mathematical Elements for Computer Graphics, second edition” by David F. Rogers and J. Alan Adams published by McGraw Hill College Divs., March 1999), for example).
A cubic Bezier surface is generally expressed by the following Equation 5. Pij in Equation 5 is a coordinate of a control point, and Ji and Kj are Bernstein functions expressed by Equation 6 and Equation 7. P(u, v) indicates a vertex coordinate on a free-form surface for particular u and v (0≦u, v≦1).
                              P          ⁡                      (                          u              ,              v                        )                          =                              ∑                          i              =              0                        3                    ⁢                                          ⁢                                    ∑                              j                =                0                            3                        ⁢                                          P                ij                            ⁢                              J                i                            ⁢                              K                j                                                                        (        5        )                                          J          i                =                                            3              !                                                      i                !                            ⁢                                                (                                      3                    -                    i                                    )                                !                                              ⁢                                                    u                i                            ⁡                              (                                  1                  -                  u                                )                                                    3              -              i                                                          (        6        )                                          K          j                =                                            3              !                                                      j                !                            ⁢                                                (                                      3                    -                    j                                    )                                !                                              ⁢                                                    u                j                            ⁡                              (                                  1                  -                  u                                )                                                    3              -              j                                                          (        7        )            
A Bezier surface is sometimes rendered directly using Equation 5 and Equation 6. In this case, an iteration method or the like is used for calculation of an edge between a curved surface and another curved surface or a projected surface, which takes an enormous amount of calculation time.
On the other hand, in order to render more quickly than such a direct rendering method, a tessellation method for calculating points on a free-form surface using a particular pair of parameters P(u, v) and rendering the surface by approximation of a collection of polygons obtained by connecting these points on the surface (See Background Art 5, Japanese Laid-Open Patent Application No. 2001-331812, for example).
Or, there is another method of rendering by polygon approximation using a so-called subdivision method, that is, the repetition of the processing of generating new control points by averaging the coordinates of adjacent control points (See Background Art 6, Japanese Laid-Open Patent Application No. 11-7544).
In the field of 3D computer graphics, not only the quality of an object shape but also the processing such as coloring and shading is an important element for determination of image quality. Since normals of an object are used for shading each surface, precise calculation of the normals is important.
However, in the conventional curved surface image processing apparatus for handling the technique A, namely, the general calculation procedures of the entire apparatus, there is a problem that an amount of data other than NURBS data increases because the conventional curved surface image processing apparatus computes each coefficient matrix at the preprocessing stage.
There is another problem that input data is limited to cubic NURBS surfaces. There is still another problem that increments of the parameters u and v are limited to fixed values (Δu, Δv) if a difference matrix is used. In addition, there is further still another problem that a coefficient matrix needs to be rationalized for strict representation of a NURBS surface and thus each point on the computed NURBS surface needs to be divided, which causes increase in an amount of computation.
Next, in order to render a NURBS surface using the above technique B, points on the NURBS surface are directly obtained for polygon division. However, this conventional method has a problem that basis functions expressed by the above Cox-de Boor's recurrence formula need to be obtained for calculating the coordinates of the points on the NURBS surface, and thus an enormous amount of computation is required.
Conventionally, a CPU performs the above-mentioned direct division of a parametric surface into polygons, namely, the tessellation processing. However, in order to represent a target 3D object more finely and closer to an actual object, the number of polygon divisions inevitably needs to be larger for approximation of the surface, and thus the load on the CPU becomes heavier. There is another problem that a computation circuit for obtaining points on a surface becomes larger in size when a circuit for dividing a parametric surface into polygons (tessellator) is integrated into hardware.
So, in order to solve these problems, the present invention does not obtain points on a NURBS surface directly, but directly obtains points on a relatively simple rational Bezier surface obtained by equivalent transformation of a NURBS surface, and then divides the rational Bezier surface into polygons. That is why it is easy to obtain control points on a rational Bezier surface by applying the subdivision method. Note that there are the Oslo algorithm and the Bohm method as methods of transforming a B-spline curve into a piecewise rational Bezier curve by knot insertion (See Background Art 7, Prautzsh, H., “A Short Proof of the Oslo Algorithm” Comp. Aid. Geom. Des., Vol. 1, pp. 95–96, 1984, and Background Art 8, Bohm, W., “Inserting New Knots into B-spline curves” Comp. Aid. Des., Vol. 12, pp. 199–201, 1980).
First, problems involving equivalent transformation of a NURBS surface into a rational Bezier surface will be described. For equivalent transformation of a NURBS surface into a rational Bezier surface, a method called knot insertion can be used. A curved surface transformation method using a knot insertion algorithm will be explained below in detail.
For the sake of simplicity, a method of transforming a NURBS curve into a rational Bezier curve will be explained first. As for knot insertion into a NURBS curve, the following algorithm is known. When the degree is n, a plurality of control points are (Q[0], Q[1], . . . , Q[I−1]) (the number of control points is I), and an initial knot vector is (u[0], u[1], . . . , u[I+n]) (the number of elements of the knot vector is I+n+1), if a new knot ˜u is inserted between the knot u[k] and u[k+1] (the position of knot insertion is k), new control points (Q′[0], Q′[1], . . . , Q′[I]) are expressed by the following equation.<Q′[i]>=(1−a[i])*<Q[i−1]>+a[i]*<Q[i]>where i is not 0. When i is 0, the control points are expressed by the following equation.<Q′[0]>=a[0]*<Q[0]>
Here, the coefficient array a[i] in the above equation is expressed by the following equation.a[i]=1 (when i is k−n or smaller)a[i]=0 (when i is k+1 or larger)a[i]=(˜u−u[i])/(u[i+n]−u[i]) (when i is any other value)
For example, when initial control points are (Q[0], Q[1], Q[2], Q[3]), an initial knot vector is (u[0], u[1], . . . , u[7]) and a new knot ˜u is inserted between a knot u[3] and a knot u[4], new control points (Q′[0], Q′[1], . . . , Q′[4]) are as follows. Since the position of knot insertion is k=3, the coefficient array is:a[0]=1a[1]=(˜u−u[1])/(u[4]−u[1])=(u[3]−u[1])/(u[4]−u[1])a[2]=(˜u−u[2])/(u[5]−u[2])=(u[3]−u[2])/(u[5]−u[2])a[3]=(˜u−u[3])/(u[6]−u[3])=0a[4]=0and using the above, the following is obtained.<Q′[0]>=a[0]*<Q[0]>=<Q[0]><Q′[1]>=(1−a[1])*<Q[0]>+a[1]*<Q[1]><Q′[2]>=(1−a[2])*<Q[1]>+a[2]*<Q[2]><Q′[3]>=(1−a[3])*<Q[2]>+a[3]*<Q[3]>=<Q[2]><Q′[4]>=(1−a[4])*<Q[3]>+a[4]*<Q[4]>=<Q[3]>
This shows that the initial control point <Q[1]> disappears and control points are generated at new positions <Q′[1]> and <Q′[2]>.
By the way, control points actually have their weights. In this case, the homogeneous coordinates transformed from the position coordinates of the control points need to be substituted into the above equations. To be more specific, when a control point is expressed by a 2D coordinate <Q[i]>=(qx[i], qy[i]) and the weight is qw[i], the homogeneous coordinate thereof <Q[i]>=(qw[i]*qx[i], qw[i]*qy[i], qw[i]) is obtained by multiplying the position coordinate by the weight. Also, when the control point coordinate is expressed by a 3D coordinate <Q[i]>=(qx[i], qy[i], qz[i]), the homogeneous coordinate <Q[i]>=(qw[i]*qx[i], qw[i]*qy[i], qw[i]*qz[i], qw[i]) is obtained. As mentioned above, the final control points are also expressed by homogeneous coordinates as a result of the above knot insertion using the control points transformed into those expressed by the homogeneous coordinates, and thus divisions by weights are required for transformation back into the control points expressed by the normal coordinates.
However, there is a problem that unnecessary control points to be abandoned are generated when equivalent transformation of a NURBS curve is performed to transform it into a rational Bezier curve using the knot insertion algorithm, and thus there occurs another problem that the number of control points to be abandoned varies depending on the elements of the initial knot vector. Therefore, only transformation of a NURBS curve into a rational Bezier curve by knot insertion does not clearly indicate the positions and the number of control points to be abandoned, and thus there occurs a problem of making subsequent subdivision processing difficult.
The problem that unnecessary control points are generated when a NURBS curve as shown in FIG. 19 is transformed into a rational Bezier curve will be explained below using a concrete example.
As the first example where unnecessary control points are generated, the NURBS curve 1901 in FIG. 19 is defined by the degree n=3, control points (Q[0], Q[1], Q[2], Q[3]) and a knot vector (u[0], u[1], . . . , u[7]). In other words, the number of control points is 4 and the number of elements of the knot vector is 8. It is assumed that u[i]<u[j] is satisfied for all the different indices i and j (i<j). Here, suppose that the final knot vector is (u′[0], u′[1], u′[2], . . . ) as a result of inserting knots one by one into the initial knot vector (u[0], u[1], . . . , u[7]). If the following relation is satisfied, the generated final NURBS curve is transformed equivalently into a single rational Bezier curve without changing the shape thereof.                u[0]=u′[0]        u[1]=u′[1]        u[2]=u′[2]        u[3]=u′[3]=u′[4]=u′[5]        u[4]=u′[6]=u′[7]=u′[8]        u[5]=u′[9]        u[6]=u′[10]        u[7]=u′[11]        
To be more specific, since the effective range of the initial knot vector of the NURBS curve is (u[3], u[4]), the final knot vector (u′[0], u′[1], u′[2], . . . , u′[11]) is obtained by inserting knots so that the multiplicities of the knots u[3] and u[4] in this range become “3” (so that the degrees thereof are both n=3) respectively. In this case, 4 knots are newly inserted. Therefore, the final number of control points becomes 8 because 4 control point are added, and thus the final control points are (Q′[0], Q′[1], . . . , Q′[7]). It is known that the NURBS curve defined by such a knot vector is equivalent to a rational Bezier curve, which completely matches the original NURBS curve in shape. Here, “the final number of control points after knot insertion” is 8 but “the number of control points that define the rational Bezier curve” is 4, so it is found that 4 control points, among the final control points, are unnecessary for representation of the rational Bezier curve.
As the second example where unnecessary control points are generated, suppose that the initial knot vector is (u[0], u[1], . . . , u[8]) by adding one more knot. It is assumed that u[i]<u[j] is satisfied for all the different indices i and j (i<j). In order to obtain a rational Bezier curve, the final knot vector (u′[0], u′[1], u′[2], . . . ) after knot insertion needs to be as follows.                u[0]=u′[0]        u[1]=u′[1]        u[2]=u′[2]        u[3]=u′[3]=u′[4]=u′[5]        u[4]=u′[6]=u′[7]=u′[8]        u[5]=u′[9]=u′[10]=u′[11]        u[6]=u′[12]        u[7]=u′[13]        u[8]=u′[14]        
To be more specific, since the effective range of the initial knot vector of the NURBS curve is (u[3], u[5]), the final knot vector (u′[0], u′[1], u′[2], . . . , u′[14]) is obtained by inserting knots so that the multiplicities of the knots u[3], u[4] and u[5] in this range become “3” (so that the degrees thereof are all n=3) respectively. In other words, “the final number of control points after knot insertion” is 11 (the number of elements of the knot vector 15−4=11). In this case, the original NURBS curve is divided into two continuous rational Bezier curves. However, since these two rational Bezier curves share one control point on their connection point, “the number of control points that define the rational Bezier curves” is 7 (4×2−1=7). Therefore, it is found here that 4 control points are also unnecessary.
However, the number of control points to be abandoned is not always 4 depending on the elements of the initial knot vector. The number of control points to be abandoned varies depending on the initial knot vector. This occurs when the initial knot vector includes knots with the same value.
To be more specific, the third example that unnecessary control points are generated is a case where an initial knot vector includes knots of u[i]=u[j] for different indices i and j (i<j). For example, in the above example, suppose that u[2] is equal to u[3] among the initial knot vector (u[0], u[1], . . . , u[8]). In order to transform the NURBS curve which is finally generated by knot insertion equivalently into two continuous rational Bezier curves, the following relation needs to be satisfied.                u[0]=u′[0]        u[1]=u′[1]        u[2]=u′[3]=u′[2]=u′[3]=u′[4]        u[4]=u′[5]=u′[6]=u′[7]        u[5]=u′[8]=u′[9]=u′[10]        u[6]=u′[11]        u[7]=u′[12]        u[8]=u′[13]        
To be more specific, since the effective range of the initial knot vector of the NURBS curve is (u[3], u[5]) and u[2] is equal to u[3], the final knot vector (u′[0], u′[1], u′[2], . . . , u′[13]) is obtained by inserting knots so that the multiplicities of the knots u[2] and u[3], and u[4] and u[5] become “3” respectively. Here, “the final number of control points after knot insertion” is 10 (14−4=10) but “the number of control points that define the rational Bezier curves” is 7 (4×2−1=7). Therefore, it is found here that 3 control points are unnecessary.
Unnecessary control points are also generated in exactly the same manner when a NURBS surface is transformed equivalently into a rational Bezier surface.
As the fourth example where unnecessary control points are generated will be explained with reference to a case of a NURBS surface. As for NURBS surface, the control points are defined by a 2D array, and the degrees and knot vectors that are parameters for basis functions are defined in the u and v directions respectively. Therefore, knot insertion in both u and v directions makes it possible to transform a NURBS surface equivalently into a rational Bezier surface.
For example, it is supposed that the number of control points Q[i][j] on a NURBS surface is 5×5=25, the degree in the u and v directions is m=n=3, the initial knot vector in the u direction is (u[0], u[1], . . . , u[8]) and the initial knot vector in the v direction is (v[0], v[1], . . . , v[8]). It is also supposed that u[i]<u[j] is satisfied in the knot vector in the u direction for all the different indices i and j (i<j), whereas v[2] is equal to v[3] and v[i]<v[j] is satisfied in the knot vector in the v direction. When the final knot vectors in the u and v directions obtained after knot insertion are (u′[0], u′[1], u′[2], . . . ) and (v′[0], v′[1], v′[2], . . . ), the following relation needs to be satisfied in order to transform the NURBS surface equivalently into a rational Bezier surface on the analogy of the above examples.                u[0]=u′[0]        u[1]=u′[1]        u[2]=u′[2]        u[3]=u′[3]=u′[4]=u′[5]        u[4]=u′[6]=u′[7]=u′[8]        u[5]=u′[9]=u′[10]=u′[11]        u[6]=u′[12]        u[7]=u′[13]        u[8]=u′[14]        v[0]=v′[0]        v[1]=v′[1]        v[2]=v[3]=v′[2]=v′[3]=v′[4]        v[4]=v′[5]=v′[6]=v′[7]        v[5]=v′[8]=v′[9]=v′[10]        v[6]=v′[11]        v[7]=v′[12]        v[8]=v′[13]        
Accordingly, “the final number of control points after knot insertion” is 110 (11×10=110) in total because the number in the u direction is 11 and that in the v direction is 10. On the other hand, “the number of control points that define a rational Bezier surface” is 49 (7×7=49) in total because the number in the u direction is 7 and that in the v direction is 7. Therefore, the number of unnecessary control points to be abandoned is 61 (110−49=61).
As described above, there is a problem that unnecessary control points are generated in the process of knot insertion when a NURBS surface is transformed into a rational Bezier surface.
Since the number of these unnecessary control points varies depending on the elements of the initial knot vector, particularly the multiplicity of the knots in the effective range of the initial knot vector, the relation between the multiplicity and the control points needs to be generalized.
The control points which are finally transformed into a rational Bezier surface by knot insertion is transferred to the subsequent block for performing polygon division using the subdivision method. Only “the control points that define the rational Bezier surface” are necessary for the subdivision, and “the control points that do not define the rational Bezier surface” are unnecessary for that purpose. Therefore, it is necessary to remove “the control points that do not define the rational Bezier surface” from “the final control points obtained after knot insertion” for reduction of the data amount.
Next, the technique C and its problem will be described. Since smoothness of a surface patch needs to be calculated on every subdivision in the subdivision processing shown in the background art 3, for example, Japanese Laid-Open Patent Application No. 11-007544 (pp. 11–14), there is a problem that an enormous amount of smoothness calculation load is put on the curved surface image processing apparatus.
Also, in the above-mentioned background art 4, Japanese Laid-Open Patent Application No. 2001-52194 (p. 5), a deviation vector of a chord cannot be used as an index for detecting a patch that forms a silhouette edge of an object (hereinafter referred to as a silhouette edge forming patch).
Next, the technique D and its problems will be described. In calculating a normal of each control point that forms a Bezier surface using the method of the above-mentioned background art 4, Japanese Laid-Open Patent Application No. 2001-52194 (p. 5), vertices on the surface are calculated by directly giving parameters such as u, v and the like to the points on the surface and then the normals of the generated points on the surface are calculated using midpoints obtained in the process of the vertex calculation. This background art 4 describes that the normal calculation on each control point on the surface patch is avoided when it is judged that the control points on the four corners and the adjacent points coincide with each other, but does not show specifically how to avoid the calculation.
The above-mentioned background art 6, Japanese Laid-Open Patent Application No. 11-7544, has a problem of an enormous amount of time for calculating a normal on a surface because it uses a common formula. Also, it uses a Coon's patch, and a normal is obtained by approximate calculation.
Further, the above-mentioned background art 5 or 6, Japanese Laid-Open Patent Application No. 2001-331812 or Japanese Laid-Open Patent Application No. 11-7544, has a problem of increase in an amount of computation because it also calculates normals of unnecessary control points when only the control points on a surface are used for final image generation.